{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Divide a Long Corridor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分隔长廊的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个图书馆的长廊里，有一些座位和装饰植物排成一列。给你一个下标从 <strong>0</strong>&nbsp;开始，长度为 <code>n</code>&nbsp;的字符串&nbsp;<code>corridor</code>&nbsp;，它包含字母&nbsp;<code>'S'</code> 和&nbsp;<code>'P'</code>&nbsp;，其中每个&nbsp;<code>'S'</code>&nbsp;表示一个座位，每个&nbsp;<code>'P'</code>&nbsp;表示一株植物。</p>\n",
    "\n",
    "<p>在下标 <code>0</code>&nbsp;的左边和下标 <code>n - 1</code>&nbsp;的右边 <strong>已经</strong>&nbsp;分别各放了一个屏风。你还需要额外放置一些屏风。每一个位置&nbsp;<code>i - 1</code> 和&nbsp;<code>i</code>&nbsp;之间（<code>1 &lt;= i &lt;= n - 1</code>），至多能放一个屏风。</p>\n",
    "\n",
    "<p>请你将走廊用屏风划分为若干段，且每一段内都 <strong>恰好有两个座位</strong>&nbsp;，而每一段内植物的数目没有要求。可能有多种划分方案，如果两个方案中有任何一个屏风的位置不同，那么它们被视为 <strong>不同</strong> 方案。</p>\n",
    "\n",
    "<p>请你返回划分走廊的方案数。由于答案可能很大，请你返回它对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;的结果。如果没有任何方案，请返回&nbsp;<code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/04/1.png\" style=\"width: 410px; height: 199px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>corridor = \"SSPPSPS\"\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>总共有 3 种不同分隔走廊的方案。\n",
    "上图中黑色的竖线表示已经放置好的屏风。\n",
    "上图每种方案中，每一段都恰好有 <strong>两个</strong>&nbsp;座位。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/04/2.png\" style=\"width: 357px; height: 68px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>corridor = \"PPSPSP\"\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>只有 1 种分隔走廊的方案，就是不放置任何屏风。\n",
    "放置任何的屏风都会导致有一段无法恰好有 2 个座位。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/12/3.png\" style=\"width: 115px; height: 68px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>corridor = \"S\"\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>没有任何方案，因为总是有一段无法恰好有 2 个座位。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == corridor.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>corridor[i]</code>&nbsp;要么是&nbsp;<code>'S'</code>&nbsp;，要么是&nbsp;<code>'P'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-divide-a-long-corridor](https://leetcode.cn/problems/number-of-ways-to-divide-a-long-corridor/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-divide-a-long-corridor](https://leetcode.cn/problems/number-of-ways-to-divide-a-long-corridor/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"SSPPSPS\"', '\"PPSPSP\"', '\"S\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        ans = 1\n",
    "        last = -1\n",
    "        cur = [-1,-1]\n",
    "        flag = True\n",
    "        MOD = 10**9+7\n",
    "        n = len(corridor)\n",
    "        for i,x in enumerate(corridor):\n",
    "            if x==\"S\":\n",
    "                if flag:\n",
    "                    cur[0] = i\n",
    "                    flag = False\n",
    "                else:\n",
    "                    flag = True\n",
    "                    cur[1] = i\n",
    "                    if last!=-1:\n",
    "                        ans = (ans*(cur[0]-last))%MOD\n",
    "                    last = cur[1]\n",
    "        if last!=-1 and flag:\n",
    "            return ans\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans, cnt_s, pre = 1, 0, -1\n",
    "        for i, x in enumerate(corridor):\n",
    "            if x == 'S':\n",
    "                cnt_s += 1\n",
    "                if cnt_s >= 3 and cnt_s % 2:\n",
    "                    ans = ans * (i - pre) % MOD\n",
    "                pre = i\n",
    "\n",
    "        if cnt_s < 2 or cnt_s % 2 == 1:\n",
    "            ans = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        prev, cnt, ans = -1, 0, 1\n",
    "        for i, ch in enumerate(corridor):\n",
    "            if ch == \"S\":\n",
    "                cnt += 1\n",
    "                if cnt >= 3 and cnt % 2 == 1:\n",
    "                    ans = ans * (i - prev) % mod\n",
    "                prev = i\n",
    "        \n",
    "        if cnt < 2 or cnt % 2 == 1:\n",
    "            ans = 0\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        ans, cnt_s, pre = 1, 0, 0\n",
    "        for i, ch in enumerate(corridor):\n",
    "            if ch == 'S':\n",
    "                # 对第 3,5,7,... 个座位，可以在其到其左侧最近座位之间的任意一个位置放置屏风\n",
    "                cnt_s += 1\n",
    "                if cnt_s >= 3 and cnt_s % 2:\n",
    "                    ans = ans * (i - pre) % 1000000007\n",
    "                pre = i  # 记录上一个座位的位置\n",
    "        return ans if cnt_s and cnt_s % 2 == 0 else 0  # 座位个数必须为正偶数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        c = Counter(corridor)\n",
    "        if 'S' not in c or c['S'] & 1 != 0: return 0\n",
    "        ans = 1\n",
    "        cnt = 0\n",
    "        cntp = 0\n",
    "        for x in corridor:\n",
    "            if x == 'S':\n",
    "                cnt += 1\n",
    "            elif cnt == 2 and x == 'P':\n",
    "                cntp += 1\n",
    "            if cnt == 3:\n",
    "                ans *= (cntp + 1) \n",
    "                ans %= 10**9 + 7\n",
    "                cnt, cntp = 1, 0\n",
    "        return ans\n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        prev, cnt, ans = -1, 0, 1\n",
    "\n",
    "        for i, ch in enumerate(corridor):\n",
    "            if ch == 'S':\n",
    "                cnt += 1\n",
    "                if cnt >=3 and cnt % 2 == 1:\n",
    "                    ans = ans * (i - 1 - (prev+1) + 1 + 1) % mod\n",
    "                prev = i\n",
    "        \n",
    "        if cnt < 2 or cnt % 2 == 1:\n",
    "            return 0\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(corridor)\n",
    "        parr = []\n",
    "        s, p = 0, 0\n",
    "        for i, c in enumerate(corridor):\n",
    "            if c == 'S':\n",
    "                s += 1\n",
    "                if s == 3:\n",
    "                    if p:\n",
    "                        parr.append(p)\n",
    "                    s, p = 1, 0\n",
    "            elif c == 'P':\n",
    "                if s == 2:\n",
    "                    p += 1\n",
    "        if s != 2:\n",
    "            return 0\n",
    "        # ans = 1\n",
    "        # for p in parr:\n",
    "        #     ans = ans * (p+1) % mod\n",
    "        # return ans\n",
    "        return reduce(lambda acc, p : acc * (p+1) % mod, parr, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numberOfWays(self, corridor):\n",
    "        \"\"\"\n",
    "        :type corridor: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ##Solution 1 记忆化搜索\n",
    "        ##state definition\n",
    "        ##i : cur position\n",
    "        ## cur: current num of seats\n",
    "\n",
    "        ###状态机DP\n",
    "        ###DP[i][cur] 第i位置 状态为1\n",
    "        n = len(corridor)\n",
    "        MOD = pow(10,9) + 7\n",
    "        a,b,c = 1,0,0\n",
    "        for i in range(1,n + 1):\n",
    "            isseat = (corridor[i - 1] == \"S\")\n",
    "            if isseat:\n",
    "                a,b,c = 0,(a + c)%MOD,b%MOD\n",
    "            else:\n",
    "                a,b,c = (a + c)%MOD,b%MOD,c%MOD\n",
    "            \n",
    "        return c % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "\n",
    "\n",
    "        last_seat = -1\n",
    "        MODX = 10**9+7\n",
    "\n",
    "        n = len(corridor)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        cnt = 0 \n",
    "        prev = -1 \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if corridor[i]=='P':\n",
    "                continue \n",
    "            if corridor[i]=='S':\n",
    "                cnt += 1\n",
    "                if cnt ==2:\n",
    "                    ans = 1 \n",
    "                    \n",
    "                if cnt>=3 and cnt%2==1:\n",
    "                    ans *= i-prev\n",
    "                    ans %= MODX \n",
    "\n",
    "                prev = i \n",
    "        if cnt%2==1:\n",
    "            return 0 \n",
    "        \n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.MODULO = 10 ** 9 + 7\n",
    "\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        retVal = 1\n",
    "\n",
    "        count = 0\n",
    "        previous = -1\n",
    "        for index, value in enumerate(corridor):\n",
    "            if value == \"S\":\n",
    "                count += 1\n",
    "\n",
    "                if (count >= 3) and (count % 2 == 1):\n",
    "                    retVal = (retVal * (index - previous)) % self.MODULO\n",
    "\n",
    "                previous = index\n",
    "\n",
    "        if (count < 2) or (count % 2 == 1):\n",
    "            retVal = 0\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        ans = 1\n",
    "        k = t = 0\n",
    "        for ch in corridor:\n",
    "            if ch == 'S':\n",
    "                if t < 2:\n",
    "                    t = t + 1\n",
    "                    k = 0\n",
    "                else:\n",
    "                    ans = (ans * (k + 1)) % 1000000007\n",
    "                    k = 0\n",
    "                    t = 1\n",
    "            else:\n",
    "                k = k + 1\n",
    "        if t < 2:\n",
    "            return 0\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        re = 1\n",
    "        seats = 0\n",
    "        plants = 0\n",
    "        flag = 0\n",
    "        nu = 0\n",
    "        for c in corridor:\n",
    "            \n",
    "            if c == 'S':\n",
    "                seats += 1\n",
    "                if seats == 1:\n",
    "                    # print(1)\n",
    "                    if nu > 0:\n",
    "                        re = re * (plants+1) % MOD\n",
    "                    plants = 0\n",
    "                elif seats == 2:\n",
    "                    # print(2)\n",
    "                    nu += 1\n",
    "                    seats = 0\n",
    "            elif c == 'P':\n",
    "                if seats == 0:\n",
    "                    # print(3)\n",
    "                    plants += 1\n",
    "            # print(re,seats,plants) \n",
    "        if nu == 0:\n",
    "            re = 0\n",
    "        elif nu == 1:\n",
    "            re = 1\n",
    "        elif seats != 0:\n",
    "            re = 0\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        ans, cnt_s, pre = 1, 0, 0\n",
    "        for i, ch in enumerate(corridor):\n",
    "            if ch == 'S':\n",
    "                # 对第 3,5,7,... 个座位，可以在其到其左侧最近座位之间的任意一个位置放置屏风\n",
    "                cnt_s += 1\n",
    "                if cnt_s >= 3 and cnt_s % 2:\n",
    "                    ans = ans * (i - pre) % 1000000007\n",
    "                pre = i  # 记录上一个座位的位置\n",
    "        return ans if cnt_s and cnt_s % 2 == 0 else 0  # 座位个数必须为正偶数\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        site = Counter(corridor)['S']\n",
    "        if site % 2 == 1 or site < 2:\n",
    "            return 0\n",
    "\n",
    "        ans = 1\n",
    "        seat = 0\n",
    "        pant = 0\n",
    "        for i, cor in enumerate(corridor) :\n",
    "            if cor == 'S' :\n",
    "                seat += 1\n",
    "                if seat == 3 :\n",
    "                    ans = (ans * (pant+1)) % mod\n",
    "                    seat = 1\n",
    "                    pant = 0\n",
    "            else :\n",
    "                if seat == 2 : \n",
    "                    pant += 1\n",
    "\n",
    "        return ans % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfWays(self, corridor: str) -> int:\r\n",
    "        MOD = 10**9 + 7\r\n",
    "        ans = 1\r\n",
    "        cnt_s = 0 \r\n",
    "        last = 0 \r\n",
    "        for i, ch in enumerate(corridor):\r\n",
    "            if ch == 'S':\r\n",
    "                cnt_s += 1\r\n",
    "                # 對於 第3,5,7,... 個座位，可以在其到其左側最近座位之間的任意一個位置放置屏風\r\n",
    "                if cnt_s >= 3 and cnt_s % 2:\r\n",
    "                    ans = (ans * (i - last)) % MOD \r\n",
    "                last = i # 上一個座位的位置\r\n",
    "        # 存在座位是0個或者奇數個的情況，此時方案數為0\r\n",
    "        return 0 if cnt_s == 0 or cnt_s % 2 != 0 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "\n",
    "        res = 1\n",
    "        cnt = 0\n",
    "        for i,v in enumerate(corridor):\n",
    "            if v == 'S':\n",
    "                cnt += 1\n",
    "                if cnt == 2:\n",
    "                    lastpos = i\n",
    "\n",
    "            if cnt > 2:\n",
    "                cnt = 1\n",
    "                res *= (i - lastpos)\n",
    "                \n",
    "        if cnt == 2:\n",
    "            return res%(10**9 + 7)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numberOfWays(self, corridor):\n",
    "        \"\"\"\n",
    "        :type corridor: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ##Solution 1 记忆化搜索\n",
    "        ##state definition\n",
    "        ##i : cur position\n",
    "        ## cur: current num of seats\n",
    "\n",
    "        ###状态机DP\n",
    "        ###DP[i][cur] 第i位置 状态为1\n",
    "\n",
    "        ### 滚动数组\n",
    "        n = len(corridor)\n",
    "        MOD = pow(10,9) + 7\n",
    "        a,b,c = 1,0,0\n",
    "        for i in range(1,n + 1):\n",
    "            isseat = (corridor[i - 1] == \"S\")\n",
    "            if isseat:\n",
    "                a,b,c = 0,(a + c)%MOD,b%MOD\n",
    "            else:\n",
    "                a,b,c = (a + c)%MOD,b%MOD,c%MOD\n",
    "        return c % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numberOfWays(self, corridor):\n",
    "        \"\"\"\n",
    "        :type corridor: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ##Solution 1 记忆化搜索\n",
    "        ##state definition\n",
    "        ##i : cur position\n",
    "        ## cur: current num of seats\n",
    "\n",
    "        ###状态机DP\n",
    "        ###DP[i][cur] 第i位置 状态为1\n",
    "\n",
    "        ### 滚动数组\n",
    "        n = len(corridor)\n",
    "        MOD = pow(10,9) + 7\n",
    "        a,b,c = 1,0,0\n",
    "        for i in range(1,n + 1):\n",
    "            isseat = (corridor[i - 1] == \"S\")\n",
    "            if isseat:\n",
    "                a,b,c = 0,(a + c)%MOD,b%MOD\n",
    "            else:\n",
    "                a,b,c = (a + c)%MOD,b%MOD,c%MOD\n",
    "        return c % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfWays(self, corridor: str) -> int:\r\n",
    "        ans, cnt_s, pre = 1, 0, 0\r\n",
    "        for i, ch in enumerate(corridor):\r\n",
    "            if ch == 'S':\r\n",
    "                # 对第 3,5,7,... 个座位，可以在其到其左侧最近座位之间的任意一个位置放置屏风\r\n",
    "                cnt_s += 1\r\n",
    "                if cnt_s >= 3 and cnt_s % 2:\r\n",
    "                    ans = ans * (i - pre) % 1000000007\r\n",
    "                pre = i  # 记录上一个座位的位置\r\n",
    "        return ans if cnt_s and cnt_s % 2 == 0 else 0  # 座位个数必须为正偶数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        left  = 0 \n",
    "        mid   = 0\n",
    "        right = 1  \n",
    "        \n",
    "        for item in corridor : \n",
    "            if item == \"S\" : \n",
    "                left = mid \n",
    "                mid, right = right, mid \n",
    "            else : \n",
    "                right = (right + left) % mod \n",
    "        \n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        prev, cnt, ans = -1, 0, 1\n",
    "        for i, ch in enumerate(corridor):\n",
    "            if ch == 'S':\n",
    "                cnt += 1\n",
    "                if cnt >= 3 and cnt % 2 == 1:\n",
    "                    ans = ans * (i - prev) % mod\n",
    "                prev = i\n",
    "        if cnt < 2 or cnt % 2 == 1:\n",
    "            return 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        cnt_S = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(corridor)\n",
    "        for c in corridor:\n",
    "            if c == 'S':\n",
    "                cnt_S += 1\n",
    "        if cnt_S % 2 or cnt_S == 0:\n",
    "            return 0\n",
    "        k = cnt_S // 2 - 1\n",
    "        i = 0\n",
    "        cnt_S = 0\n",
    "        ans = 1\n",
    "        while i < n and k:\n",
    "            if corridor[i] == 'S':\n",
    "                cnt_S += 1\n",
    "                if cnt_S == 2:\n",
    "                    res = 1\n",
    "                    i += 1\n",
    "                    while corridor[i] == 'P':\n",
    "                        i += 1\n",
    "                        res += 1\n",
    "                    ans = (ans * res) % MOD\n",
    "                    cnt_S = 0\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        prev, ans, cnt = -1, 1, 0\n",
    "\n",
    "        for i, ch in enumerate(corridor):\n",
    "            if ch == 'S':\n",
    "                cnt += 1\n",
    "                if cnt >= 3 and cnt % 2 == 1:\n",
    "                    ans = ans * (i - prev) % mod\n",
    "                prev = i\n",
    "        \n",
    "        if cnt < 2 or cnt % 2 == 1:\n",
    "            return 0\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "\n",
    "        res = 1\n",
    "        cnt = 0\n",
    "        for i,v in enumerate(corridor):\n",
    "            if v == 'S':\n",
    "                cnt += 1\n",
    "            if cnt > 2:\n",
    "                cnt = 1\n",
    "                res *= (i - lastpos)\n",
    "            \n",
    "            if cnt == 2 and v == 'S':\n",
    "                lastpos = i\n",
    "                \n",
    "        if cnt == 2:\n",
    "            return res%(10**9 + 7)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        sCount = Counter(corridor)['S']\n",
    "        if sCount % 2 != 0 or sCount == 0:\n",
    "            return 0\n",
    "        \n",
    "        res = 0\n",
    "        count = 0\n",
    "        ways = []\n",
    "        for i in range(len(corridor)):\n",
    "            if corridor[i] == 'S':\n",
    "                if count == 2:\n",
    "                    res += 1\n",
    "                    ways.append(res)\n",
    "                    res = 0\n",
    "                    count = 1\n",
    "                else:\n",
    "                    count += 1\n",
    "            else:\n",
    "                if count == 2:\n",
    "                    res += 1\n",
    "\n",
    "\n",
    "        mod = (10 ** 9 + 7)\n",
    "        res = 1\n",
    "        for x in ways:\n",
    "            res = res * x % mod\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        # 乘法原理，每两个座位之间的植物数量+1，就是屏风能够放的位置数量\n",
    "        MOD = 10**9+7\n",
    "        n = len(corridor)\n",
    "        nums = [1 if corridor[i]=='S' else 0 for i in range(n)]\n",
    "        total = sum(nums)\n",
    "        if total==0 or total%2!=0: return 0\n",
    "        if total==2: return 1\n",
    "\n",
    "        i = 0\n",
    "        one_num = 0\n",
    "        res = 1\n",
    "        while i<n:\n",
    "            if nums[i]==1:\n",
    "                one_num += 1\n",
    "                if one_num == 2:\n",
    "                    i += 1\n",
    "                    mid = 0\n",
    "                    while i<n and nums[i]==0:\n",
    "                        mid += 1\n",
    "                        i+=1\n",
    "                    if i<n:\n",
    "                        res = (res * (mid+1))%MOD\n",
    "                        one_num = 1\n",
    "                    pass\n",
    "            i+=1\n",
    "        \n",
    "        return res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        xx=[]\n",
    "        s=0\n",
    "        f=0\n",
    "        r=1\n",
    "        p=0\n",
    "        md=1000000007\n",
    "        cd=list(corridor)\n",
    "        #print('1:',cd)\n",
    "        c=len(cd)\n",
    "        i=0\n",
    "        while i<c and cd[i]=='P':\n",
    "            i+=1\n",
    "        \n",
    "        while c>i and cd[c-1]=='P':\n",
    "            c-=1\n",
    "        if i+2>c:\n",
    "            return 0\n",
    "\n",
    "        for j in range(i,c):\n",
    "            #print('i=',i)\n",
    "            if cd[j]=='S':\n",
    "                s+=1\n",
    "                #print('s=',s)\n",
    "                if s==2:\n",
    "                    s=0\n",
    "                    f=1\n",
    "                    p=0\n",
    "                else:\n",
    "                    f=0\n",
    "                    r*=(p+1)\n",
    "                    r%=md\n",
    "                    #print('r=',r)\n",
    "            if cd[j]=='P':\n",
    "                if f==1:\n",
    "                    p+=1\n",
    "        if s==1:\n",
    "            return 0\n",
    "        return r\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(corridor)\n",
    "        nums = [1 if corridor[i]=='S' else 0 for i in range(n)]\n",
    "        total = sum(nums)\n",
    "        if total==0 or total%2!=0: return 0\n",
    "        if total==2: return 1\n",
    "\n",
    "        i = 0\n",
    "        one_num = 0\n",
    "        res = 1\n",
    "        while i<n:\n",
    "            if nums[i]==1:\n",
    "                one_num += 1\n",
    "                if one_num == 2:\n",
    "                    i += 1\n",
    "                    mid = 0\n",
    "                    while i<n and nums[i]==0:\n",
    "                        mid += 1\n",
    "                        i+=1\n",
    "                    if i<n:\n",
    "                        res = (res * (mid+1))%MOD\n",
    "                        one_num = 1\n",
    "                    pass\n",
    "            i+=1\n",
    "        \n",
    "        return res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(corridor)\n",
    "        nums = [1 if corridor[i]=='S' else 0 for i in range(n)]\n",
    "        total = sum(nums)\n",
    "        if total==0 or total%2!=0: return 0\n",
    "        if total==2: return 1\n",
    "\n",
    "        i = 0\n",
    "        one_num = 0\n",
    "        res = 1\n",
    "        while i<n:\n",
    "            if nums[i]==1:\n",
    "                one_num += 1\n",
    "                if one_num == 2:\n",
    "                    i += 1\n",
    "                    mid = 0\n",
    "                    while i<n and nums[i]==0:\n",
    "                        mid += 1\n",
    "                        i+=1\n",
    "                    if i<n:\n",
    "                        res *= (mid+1)\n",
    "                        one_num = 1\n",
    "                    pass\n",
    "            i+=1\n",
    "        \n",
    "        return res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        s_idxer = [i for i, ch in enumerate(corridor) if ch == 'S']\n",
    "        n = len(s_idxer)\n",
    "        if n % 2 == 1 or n < 2:\n",
    "            return 0\n",
    "            \n",
    "        res = 1\n",
    "        for i in range(2, n, 2):\n",
    "            res = res * (s_idxer[i] - s_idxer[i-1]) % MOD\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        s_idxer = [i for i, ch in enumerate(corridor) if ch == 'S']\n",
    "        n = len(s_idxer)\n",
    "        if n % 2 == 1 or n < 2:\n",
    "            return 0\n",
    "        res = 1\n",
    "        for i in range(2, n, 2):\n",
    "            res = res * (s_idxer[i] - s_idxer[i-1]) % MOD\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        A = [i for i, char in enumerate(corridor) if char == 'S']\n",
    "        if not A or len(A) % 2:\n",
    "            return 0\n",
    "        res, mod = 1, 10**9+7\n",
    "        for i in range(2, len(A), 2):\n",
    "            res *= A[i]-A[i-1]\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        s_idxer = [i for i, ch in enumerate(corridor) if ch == 'S']\n",
    "        n = len(s_idxer)\n",
    "        if n % 2 == 1 or n < 2:\n",
    "            return 0\n",
    "        res = 1\n",
    "        for i in range(2, n, 2):\n",
    "            res *= s_idxer[i] - s_idxer[i-1]\n",
    "\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        mod = 10**9+7\n",
    "\n",
    "        if corridor.count('S')<2:\n",
    "            return 0\n",
    "        elif corridor.count('S')==2:\n",
    "            return 1\n",
    "        elif corridor.count('S')%2!=0:\n",
    "            return 0\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        indexs = list()\n",
    "        n = len(corridor)\n",
    "        cur = 0\n",
    "        cnt = 0\n",
    "        while cur<n:\n",
    "            if corridor[cur]=='S':\n",
    "                cnt += 1\n",
    "\n",
    "            if cnt==1 and corridor[cur]=='S':\n",
    "                indexs.append(cur)\n",
    "            elif cnt==2:\n",
    "                indexs.append(cur)\n",
    "                cnt = 0\n",
    "            \n",
    "            cur += 1\n",
    "        \n",
    "        indexs = indexs[1:-1]\n",
    "        m = len(indexs)\n",
    "        i = 0\n",
    "        while i<m-1:\n",
    "            ed = indexs[i]\n",
    "            st = indexs[i+1]\n",
    "            res *= st-ed\n",
    "\n",
    "            i += 2\n",
    "\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        n = len(corridor)\n",
    "        a = [1 if c == 'S' else 0 for c in corridor]\n",
    "        presum = [0]\n",
    "        for x in a:\n",
    "            presum.append(presum[-1] + x)\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            x = presum[i + 1]\n",
    "            if x % 2 != 0:\n",
    "                continue\n",
    "            \n",
    "            if x == 2:\n",
    "                f[i] = 1\n",
    "                continue\n",
    "            \n",
    "            if a[i] == 0:\n",
    "                f[i] = f[i - 1]\n",
    "                continue\n",
    "            l = bisect.bisect_left(presum,x - 2)\n",
    "            r = bisect.bisect_right(presum,x - 2)\n",
    "\n",
    "            f[i] = (r - l) * f[r - 2] % mod\n",
    "\n",
    "        # print(f)\n",
    "        return f[n - 1] % mod\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        n = len(corridor)\n",
    "        a = [1 if c == 'S' else 0 for c in corridor]\n",
    "        presum = [0]\n",
    "        for x in a:\n",
    "            presum.append(presum[-1] + x)\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "        last = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x = presum[i + 1]\n",
    "            if x % 2 != 0:\n",
    "                continue\n",
    "            \n",
    "            if x == 2:\n",
    "                f[i] = 1\n",
    "                continue\n",
    "            \n",
    "            if a[i] == 0:\n",
    "                f[i] = f[i - 1]\n",
    "                continue\n",
    "\n",
    "            l = bisect.bisect_left(presum,x - 2)\n",
    "            r = bisect.bisect_right(presum,x - 2)\n",
    "\n",
    "            f[i] = (r - l) * f[r - 2] % mod\n",
    "\n",
    "        # print(f)\n",
    "        return f[n - 1] % mod\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "        sLen = len(corridor)\n",
    "        mod = 1e9+7\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        seats = []\n",
    "        start = -1\n",
    "        \n",
    "        for i in range(sLen):\n",
    "            if corridor[i] == 'S':\n",
    "                count += 1\n",
    "                if start != -1:\n",
    "                    seats.append([start, i])\n",
    "                    start = -1\n",
    "                else:\n",
    "                    start = i\n",
    "                    \n",
    "        #print(seats)\n",
    "        \n",
    "        if count==0 or count %2 != 0:\n",
    "            return 0\n",
    "        \n",
    "        group = len(seats)\n",
    "        if group == 1:\n",
    "            return 1\n",
    "        \n",
    "        ans = 1\n",
    "        for i in range(group-1):\n",
    "            pCount = seats[i+1][0] - seats[i][1]\n",
    "            ans *= pCount\n",
    "            ans = int(ans%mod)\n",
    "            \n",
    "        return int(ans%mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, corridor: str) -> int:\n",
    "\n",
    "\n",
    "        last_seat = -1\n",
    "        MODX = 10**9+7\n",
    "\n",
    "        n = len(corridor)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        dp = [[0]*2 for _ in range(n+1)]\n",
    "\n",
    "        # dp[i][0] exactly dividing\n",
    "        # dp[i][1] the last few plants can be put in a room\n",
    "        dp[0][0] = 1\n",
    "        dp[0][1] = 1\n",
    "\n",
    "        if corridor[0]=='S':\n",
    "            last_seat = 1\n",
    "        if corridor[1]=='S':\n",
    "            last_seat = 2 \n",
    "        \n",
    "        if corridor[0]=='S' and corridor[1]=='S':\n",
    "            dp[2][0] = 1\n",
    "            dp[2][1] = 1\n",
    "        if corridor[0]=='P' and corridor[1]=='S':\n",
    "            dp[1][1] = 1\n",
    "        if corridor[0]=='P' and corridor[1]=='P':\n",
    "            dp[1][1] = 1\n",
    "            dp[2][1] = 1\n",
    "        \n",
    "        for i in range(3,n+1):\n",
    "            if corridor[i-1]=='P':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = dp[i-1][0]+dp[i-1][1]\n",
    "\n",
    "                dp[i][0] %=MODX\n",
    "                dp[i][1] %= MODX\n",
    "                continue \n",
    "            if last_seat == -1:\n",
    "                last_seat = i \n",
    "            else:\n",
    "                \n",
    "                dp[i][0] = dp[last_seat-1][1]\n",
    "                dp[i][1] = dp[i][0]\n",
    "\n",
    "                dp[i][0] %=MODX\n",
    "                dp[i][1] %= MODX\n",
    "                last_seat = i\n",
    "       \n",
    "        return dp[n][0]%MODX\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
